package algorithm;

import DualRepresentation.DualGraph;
import DualRepresentation.DualNode;

import utilities.Global;
import utilities.MinPriorityQueue;

public class SimpleDijkstra {

	private DualGraph graph;
	private int size;

	// the predecessor matrix
	private int[][] predecessorMatrix;

	// the origin Adjacency matrix
	private final int[][] adjacencyMatrix;

	// minimum priority queue
	private MinPriorityQueue minPriorityQ;

	private int[] doneNodes;
	private int source;

	public SimpleDijkstra(DualGraph graph) {
		this.graph = graph;
		this.size = graph.getSize();
		this.adjacencyMatrix = graph.getEdges();
		this.predecessorMatrix = new int[size][size];
		this.minPriorityQ = new MinPriorityQueue();
	}

	// The Algorithm
	public int[] run_dijkstra() {

		doneNodes = new int[size];

		initializeSingleSource();

		minPriorityQ.addAll(this.adjacencyMatrix[source]);

		DualNode u = minPriorityQ.extractMin(graph);

		while ((u != null) && (u.getDistance() < Global.INFINITY)) {

			int uIndex = u.getId();

			// for each vertex v in adj(u)
			for (int i = 0; i < size; i++) 
				if (adjacencyMatrix[uIndex][i] < Global.INFINITY) 
					relax(uIndex, i);

			u = minPriorityQ.extractMin(graph);

		}

		return doneNodes;
	}

	private void initializeSingleSource() {

		for (int i = 0; i < size; i++) {
			doneNodes[i] = Global.INFINITY;
			predecessorMatrix[source][i] = Global.UNDEFINED;
		}
		doneNodes[source] = 0;
		predecessorMatrix[source][source] = source;
		
		DualNode twin = graph.getNode(source).getTwin();
		if(twin != null){
			doneNodes[twin.getId()] = 0;
			predecessorMatrix[source][twin.getId()] = source;
		}
	}

	private void relax(int u, int v) {

		if (doneNodes[v] > doneNodes[u] + adjacencyMatrix[u][v]) {
			
			doneNodes[v] = doneNodes[u] + adjacencyMatrix[u][v];
			predecessorMatrix[source][v] = u;
			
			graph.getNode(v).setDistance(doneNodes[v]);
			minPriorityQ.add(graph.getNode(v));
			
		}

	}

	public int[][] run_all_pairs() {
		
		int[][] allPairsMatrix = new int[size][size];

		for (int i = 0; i < size; i++) {
			setSource(i);
			allPairsMatrix[i] = run_dijkstra();
		}
		return allPairsMatrix;
	}

	private void setSource(int source) {
		this.source = source;
	}

	public int[][] getPredecessorMatrix() {
		return this.predecessorMatrix;
	}

}
